package com.mlamp.二分查找;

public class 有序数组中的单一元素 {

    public static void main(String[] args) {
        有序数组中的单一元素 instance = new 有序数组中的单一元素();
        int inputs[] = new int[]{
                1, 1, 2, 3, 3, 4, 4, 8, 8
        };
        inputs = new int[]{
                3, 3, 7, 7, 10, 11, 11
        };

        int i = instance.singleNonDuplicate(inputs);
        System.out.println(i);
    }


    public Integer singleNonDuplicate3(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        if (nums.length == 1) return nums[0];
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + ((hi - lo) >> 1);
            //后半截是否是偶数
            boolean flag = (hi - mid) % 2 == 0;
            if (nums[mid] == nums[mid - 1]) {
                if (flag) {
                    hi = mid - 2;
                } else {
                    lo = mid + 1;
                }
            } else if (nums[mid] == nums[mid + 1]) {
                if (flag) {
                    hi = mid - 1;
                } else {
                    lo = mid + 2;
                }
            }
        }
        return nums[lo];
    }


    public int singleNonDuplicate2(int[] nums) {
        if (nums == null || nums.length == 0) return -1;
        if (nums.length == 1) return nums[0];
        int lo = 0;
        int hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + ((hi - lo) >> 1);
            boolean judge = (hi - mid) % 2 == 0;
            if (nums[mid] == nums[mid - 1]) {
                if (judge) {
                    hi = mid - 2;
                } else {
                    lo = mid + 1;
                }
            } else if (nums[mid] == nums[mid + 1]) {
                if (judge) {
                    hi = mid - 1;
                } else {
                    lo = mid + 2;
                }
            }
        }
        return nums[lo];
    }


    public int singleNonDuplicate(int[] nums) {

        if (nums == null || nums.length == 0) return -1;
        if (nums.length == 1) return nums[0];
        int lo = 0;
        int hi = nums.length - 1;

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            boolean halvesAreEven = (hi - mid) % 2 == 0;
            if (nums[mid + 1] != nums[mid] && nums[mid - 1] != nums[mid]) {
                return nums[mid];
            } else if (nums[mid + 1] == nums[mid]) {
                if (halvesAreEven) {
                    lo = mid + 2;
                } else {
                    hi = mid - 1;
                }
            } else {
                if (halvesAreEven) {
                    hi = mid - 2;
                } else {
                    lo = mid + 1;
                }
            }
        }
        return nums[lo];
    }
}
